package 堆;

public class Leedcode215数组中的第K个最大元素 {
    public static void main(String[] args) {
        int[] arr = {7,6,5,4,3,2,1};
        Leedcode215数组中的第K个最大元素 o = new Leedcode215数组中的第K个最大元素();
        System.out.println(o.findKthLargest(arr, 2));
    }


    public int findKthLargest(int[] nums, int k) {
        return help(nums,0,nums.length-1,k);
    }

    public int help(int[] arr ,int l,int r,int k){
        int site = quickSortIntonor(arr,l,r);
        if(site == arr.length - k){
            return arr[site];
        }else if(site < arr.length - k){//小于k大元素的位置，向右寻找
            return help(arr,site+1,r,k);
        }else{
            return help(arr,0,site-1,k);
        }
    }
    //通过快排的分区点来寻找第k大元素，第k大元素的位置在nums。length-k的位置，
    //所以如果分区的位置恰好是num.length - k,直接返回当前的分区点
    public int quickSortIntonor(int[] arr,int l,int r){
        int point = arr[l];
        int j = l;//比point小的元素区间[l+1,j],将j定义为l，确保初始状态比point小的节点个数为空
        for(int i = j + 1;i <= r;i++){//比point大的元素区间[j+1,i),将j定义为j+1，前闭后开、确保初始状态比point大的节点个数为空
            if(arr[i] < point){
                swap(arr,i ,j+1);
                j++;
            }
        }
        //循环结束，交换j和point的位置
        swap(arr,l,j);//j为小于point的最后一个元素。
        return j;
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
